Digital transmission, and in particular radio beam transmission, is frequently subjected to interference, usually involuntary interference, which gives rise to errors in the received stream. Therefore, in order to recover the information in spite of interference, it is practically essential to encode the stream to be transmitted by means of an error-correcting code, and to decode the received stream by means of an error-correcting decoder.
The error-correcting codes that are the most widespread at present are block codes and convolution codes.
Block codes are simpler and consist of adding a determined number of redundancy bits to each block of bits to be transmitted. These are low performance codes and they cannot be used for messages that run the risk of a high level of interference.
Convolution codes are much more complex, but they also provide much better performance. They cause an initial stream to be transmitted to correspond to a stream which is actually transmitted in which the number of bits is multiplied by a given factor n, e.g. a factor of 2 or a factor of 3, with each group of n bits created in this way for each initial bit depending on the preceding groups.
There are two techniques in general use for error-correcting decoding of digital streams encoded by a convolution type code:
A first technique is to use the Viterbi algorithm which consists in examining all possible cases over a very large number of cases and then in selecting the most probable case. This algorithm is optimal, but it is complex to implement.
A second solution is to use "sequential decoding" which is less than optimal but which, in contrast, is quicker and simpler to implement, particularly for complicated codes. The complexity of the sequential algorithm does not increase with code performance, and it is therefore suitable for decoding high performance codes.
Two algorithms and their variants are in general use for performing sequential decoding: the stack algorithm, and the FANO algorithm which is now somewhat outdated.
In the stack algorithm, decoding is performed in blocks (e.g. blocks of 1000 bits), and it consists in establishing a "path" through a binary "logic tree" which is a representation of the decoding, each node of the tree being defined by a depth representative of its distance from the root node of the tree, and possessing, for the bit stream under consideration, a probability defined by a numerical value called the "metric". Observed nodes are then placed in an ordered stack with the highest-metric node being extended each time by its two successors.
More precisely, for each group of received code bits in the transmitted stream corresponding to a single bit prior to encoding:
the node at the top of the stack is removed;
the metrics of the two nodes following this node are then calculated;
they are placed in the stack; and
the stack is finally sorted by nodes of decreasing metric.
When the limiting size of the stack is exceeded (i.e. when the stack overflows), the block is declared badly received and is not decoded. A request may then be made for the block to be retransmitted, or else it may be considered as being lost. Typically, the maximum size of the stack lies in the range one to ten times the number of bits in a block to be decoded. The smaller the stack the larger the number of blocks that will not be decoded (the stack will overflow often), and the larger the stack the larger the number of blocks that will be decoded with the risk of erroneously decoding blocks that have been very badly received.
The main drawbacks of stack decoding are the following: a large stack is required (stack depth is typically between one and ten times the size of blocks to be decoded, and thus between 1000 and 10,000 if 1000-bit blocks are being decoded); sorting the stack by increasing order of node metric is slow (yet the stack must be sorted each time a new node is scanned, thus between one and ten times per decoded bit); and once a block has been decoded, it is necessary to perform a trace-back in order to determine which block was, in fact, transmitted. These drawbacks make it very difficult to provide a practical implementation of such a decoder because of its size and because of the large amount of processing per decoded bit which limits its speed. In existing implementations, the stack is implemented using random access memory (RAM) which is sorted each time a node is scanned.
The invention seeks to remedy these drawbacks and to make it possible to implement such a sequential decoder at reduced cost in size and in components, and capable of operating at a high rate.